142. Linked List Cycle II
Medium

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Notice that you should not modify the linked list.

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

 

Constraints:

  • The number of the nodes in the list is in the range [0, 104].
  • -105 <= Node.val <= 105
  • pos is -1 or a valid index in the linked-list.

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Accepted
464,433
Submissions
1,145,107
Seen this question in a real interview before?
Companies

Average Rating: 4.44 (94 votes)

Premium

Approach 1: Hash Table

Intuition

If we keep track of the nodes that we've seen already in a Set, we can traverse the list and return the first duplicate node.

Algorithm

First, we allocate a Set to store ListNode references. Then, we traverse the list, checking visited for containment of the current node. If the node has already been seen, then it is necessarily the entrance to the cycle. If any other node were the entrance to the cycle, then we would have already returned that node instead. Otherwise, the if condition will never be satisfied, and our function will return null.

The algorithm necessarily terminates for any list with a finite number of nodes, as the domain of input lists can be divided into two categories: cyclic and acyclic lists. An acyclic list resembles a null-terminated chain of nodes, while a cyclic list can be thought of as an acyclic list with the final null replaced by a reference to some previous node. If the while loop terminates, we return null, as we have traversed the entire list without encountering a duplicate reference. In this case, the list is acyclic. For a cyclic list, the while loop will never terminate, but at some point the if condition will be satisfied and cause the function to return.

Complexity Analysis

  • Time complexity : O(n)O(n)

    For both cyclic and acyclic inputs, the algorithm must visit each node exactly once. This is transparently obvious for acyclic lists because the nnth node points to null, causing the loop to terminate. For cyclic lists, the if condition will cause the function to return after visiting the nnth node, as it points to some node that is already in visited. In both cases, the number of nodes visited is exactly nn, so the runtime is linear in the number of nodes.

  • Space complexity : O(n)O(n)

    For both cyclic and acyclic inputs, we will need to insert each node into the Set once. The only difference between the two cases is whether we discover that the "last" node points to null or a previously-visited node. Therefore, because the Set will contain nn distinct nodes, the memory footprint is linear in the number of nodes.



Approach 2: Floyd's Tortoise and Hare

Intuition

What happens when a fast runner (a hare) races a slow runner (a tortoise) on a circular track? At some point, the fast runner will catch up to the slow runner from behind.

Algorithm

Floyd's algorithm is separated into two distinct phases. In the first phase, it determines whether a cycle is present in the list. If no cycle is present, it returns null immediately, as it is impossible to find the entrance to a nonexistant cycle. Otherwise, it uses the located "intersection node" to find the entrance to the cycle.

Phase 1

Here, we initialize two pointers - the fast hare and the slow tortoise. Then, until hare can no longer advance, we increment tortoise once and hare twice.[1] If, after advancing them, hare and tortoise point to the same node, we return it. Otherwise, we continue. If the while loop terminates without returning a node, then the list is acyclic, and we return null to indicate as much.

To see why this works, consider the image below:

Diagram of cyclic list

Here, the nodes in the cycle have been labelled from 0 to C1C-1, where CC is the length of the cycle. The noncyclic nodes have been labelled from F-F to -1, where FF is the number of nodes outside of the cycle. After FF iterations, tortoise points to node 0 and hare points to some node hh, where Fh(modC)F \equiv h \pmod C. This is because hare traverses 2F2F nodes over the course of FF iterations, exactly FF of which are in the cycle. After ChC-h more iterations, tortoise obviously points to node ChC-h, but (less obviously) hare also points to the same node. To see why, remember that hare traverses 2(Ch)2(C-h) from its starting position of hh:

h+2(Ch)=2ChCh(modC) \begin{aligned} h + 2(C-h) &= 2C - h \\ &\equiv C-h \pmod C \end{aligned}

Therefore, given that the list is cyclic, hare and tortoise will eventually both point to the same node, known henceforce as the intersection.

Phase 2

Given that phase 1 finds an intersection, phase 2 proceeds to find the node that is the entrance to the cycle. To do so, we initialize two more pointers: ptr1, which points to the head of the list, and ptr2, which points to the intersection. Then, we advance each of them by 1 until they meet; the node where they meet is the entrance to the cycle, so we return it.

Use the diagram below to help understand the proof of this approach's correctness.

Phase 2 diagram

We can harness the fact that hare moves twice as quickly as tortoise to assert that when hare and tortoise meet at node hh, hare has traversed twice as many nodes. Using this fact, we deduce the following:

To compute the intersection point, let's note that the hare has traversed twice as many nodes as the tortoise, i.e. 2d(tortoise)=d(hare)2d(\text{tortoise}) = d(\text{hare}), that means

2(F+a)=F+nC+a2(F + a) = F + nC + a, where nn is some integer.

Hence the coordinate of the intersection point is F+a=nCF + a = nC.

To see the entire algorithm in action, check out the animation below:

Current
12 / 13

Complexity Analysis

  • Time complexity : O(n)O(n)

    For cyclic lists, hare and tortoise will point to the same node after F+ChF+C-h iterations, as demonstrated in the proof of correctness. F+ChF+C=nF+C-h \leq F+C = n, so phase 1 runs in O(n)O(n) time. Phase 2 runs for F<nF < n iterations, so it also runs in O(n)O(n) time.

    For acyclic lists, hare will reach the end of the list in roughly n2\dfrac{n}{2} iterations, causing the function to return before phase 2. Therefore, regardless of which category of list the algorithm receives, it runs in time linearly proportional to the number of nodes.

  • Space complexity : O(1)O(1)

    Floyd's Tortoise and Hare algorithm allocates only pointers, so it runs with constant overall memory usage.

Footnotes


  1. It is sufficient to check only hare because it will always be ahead of tortoise in an acyclic list. ↩︎

Report Article Issue

Comments: 44
mglezer's avatar
Read More

F = b is incorrect, which is obvious when F is very large and C is very small. Rather, from 2*d(tortoise) = d(hare), we have 2(F+a) = F+nC+a, for some integer n, so F+a = nC, or F = nC-a. In phase two, you dispatch another tortoise from the head of the list, and slow down the hare in the cycle to advance one node per step. After F steps the tortoise will travel F nodes, and the hare will travel F=nC-a nodes. The hare started at F+a = F+a%C, so the hare's position after F steps is F+(a+F)%C = F+(a+nC-a)%C = F. So the tortoise and the (slow) hare will meet at the start of the cycle.

163
Show 23 replies
Reply
Share
Report
henrykira's avatar
Read More

Please, fix your output statement in the description....I felt like I need to output a string.
Why do you put something like "Output: tail connects to node index 0" when you actually want "Node"?

66
Show 4 replies
Reply
Share
Report
wise666's avatar
Read More

I don't think this solution is faithfulness enough. The F should be equals to nC+b, (n>=0)rather than b, since F may be very large, but b may be very small.
But the method still works well.

26
Reply
Share
Report
alementuev's avatar
Read More
42
Show 3 replies
Reply
Share
Report
topcoder811's avatar
Read More

F != h (mod C) . its other way around h = F (mod C). Please fix it.

13
Show 3 replies
Reply
Share
Report
LumCoder's avatar
Read More

Can someone explain why the intersection point is naturally the point that its distance to the cycle entrance is the same as the distance from the beginning to the cycle entrance?

11
Show 1 reply
Reply
Share
Report
kkk20080142's avatar
Read More

The proof of F=b is wrong, instead it should be F=b (mod C)

7
Show 1 reply
Reply
Share
Report
ryanleitaiwan's avatar
Read More

If you prefer simple math and don't care about modular arithmetic for a formal proof, I personally understand why Floyd's algorithm works using this simple case.

Algorithm: Assume non-cyclic length N and cyclic length M with index [0,M-1]

<-  N  ->          1. When slow enters the cycle at 0 (◎), fast is at N (■)
        s
□-□-□-□-◎-□-□-□    2. Fast is M-N behind, so they will meet at M-N (※)
        |     |
        □  M  ■ f  3. Cycle entrance is now M-(M-N) = N away, so if we
        |     |       make one pointer start over and both at slow speed,
        □-□-※-□       they will guarantee to meet again at 0 (◎)
           meet

2
Reply
Share
Report
dance-henry's avatar
Read More

There is actually an easier way to understand how the phase 2 works. From the explanation of phase 1, we know if it is cyclic then hare and tortoise will meet at (C- h) mod C. Therefore, the distance between intersection and the entrance is "h mod C". On the other hand, the distance between HEAD node and the entrance node is F, and we had the assumption which is F = h mod C. Therefore the next meeting point will be the entrance node.

2
Reply
Share
Report
twicetzuyufan's avatar
Read More

Why does it not work when I start with the slow pointer equal to the head and the fast pointer equal to head.next? It worked for the Linked-List-Cycle 1 problem but here it gives me TLE, and the solution works when I start both pointers at the head and do the equality check after moving the pointers.

For reference this is the TLE code for this problem:

 public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null){
            if(slow == fast){
                fast = head;
                while(fast != slow){
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
            
            slow = slow.next;
            fast = fast.next.next;
            
        }
        return null;
    }

while a similar idea for Linked List Cycle 1 works fine:

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        ListNode fastPointer = head.next;
        ListNode slowPointer = head;
        while(fastPointer != null && fastPointer.next != null){
            if(fastPointer == slowPointer) return true;
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
        }
        return false;
    }
}

1
Show 2 replies
Reply
Share
Report
Success
Details
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Linked List Cycle II.
Memory Usage: 7.6 MB, less than 29.51% of C++ online submissions for Linked List Cycle II.
Time Submitted
Status
Runtime
Memory
Language
06/15/2021 09:12Accepted0 ms7.6 MBcpp
07/27/2020 08:51Accepted8 ms7.7 MBcpp
07/27/2020 08:50Wrong AnswerN/AN/Acpp
/23
Contribute
|||
Saved
Trie
This list is empty.